Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,

• [1,1,2] have the following unique permutations:
  
• [1,1,2], [1,2,1], and [2,1,1].

题目大意：给定一个有重复数字的数组，返回全排列

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/5/22
 * 递归解法
 * 与46的区别，关键在于去重
 * 去重的思想是，先排序，如果nums[1]与nums[2]重复，那么在nums[1]未参与组合前，nums[2]也不参与组合
 */
public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        boolean[] flag = new boolean[nums.length];
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        Arrays.sort(nums);
        permuteRecursion(result, nums, tmp, flag);
        return result;
    }

    public void permuteRecursion(List<List<Integer>> result, int[] nums, ArrayList<Integer> tmp, boolean[] flag) {
        int len = nums.length;

        if (tmp.size() == len) {
            result.add((List<Integer>) tmp.clone());
            return;
        }

        for (int i = 0; i < len; i++) {
            if (flag[i] || i > 0 && nums[i] == nums[i -1 ] && !flag[i - 1]) continue;

            flag[i] = true;
            tmp.add(nums[i]);
            permuteRecursion(result, nums, tmp, flag);
            tmp.remove(tmp.size() - 1);
            flag[i] = false;
        }
    }
}